/*
https://leetcode.cn/problems/qie-fen-shu-zu/solution/qie-fen-shu-zu-zhi-shu-shai-dp-by-leetcode-solutio/
 */
import java.util.Arrays;

public class SolutionLCP14 {
    public int splitArray(int[] nums) {
        int n=nums.length,m= Arrays.stream(nums).max().getAsInt();
        int[] minPrime=new int[1000010];
        int[] prime=new int[100010];
        int[] g=new int[1000010];
        for (int i=2;i<=m;i++){
            if (minPrime[i]==0){
                prime[++prime[0]]=i;
                minPrime[i]=i;
            }
            for (int j=1;j<=prime[0];j++){
                if (i>m/prime[j]){
                    break;
                }
                minPrime[i*prime[j]]=prime[j];
                if (i%prime[j]==0){
                    break;
                }
            }
        }
        for (int i=1;i<=prime[0];i++){
            g[prime[i]]=n;
        }
        for (int x=nums[0];x>1;x/=minPrime[x]){
            g[minPrime[x]]=0;
        }
        int ans=1;
        for (int i=0;i<n;i++){
            ans=i+1;
            for (int x=nums[i];x>1;x/=minPrime[x]){
                ans=Math.min(g[minPrime[x]]+1,ans);
            }
            if (i==n-1){
                break;
            }
            for (int x=nums[i+1];x>1;x/=minPrime[x]){
                g[minPrime[x]]=Math.min(g[minPrime[x]],ans);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP14().splitArray(new int[]{2,3,3,2,3,3}));
    }
}
